﻿using System;
using System.Collections.Generic;
using System.Text;


public class BiTreeExample
{
    // 从二叉树中找寻值为 value 的结点
    TreeNode<int> Search(TreeNode<int> root, int value)
    {
        TreeNode<int> p = root;
        if (p == null)
        {
            return null;
        }

        if (p.Data.Equals(value))
        {
            return p;
        }

        if (p.LChild != null)
        {
            return Search(p.LChild, value);
        }

        if (p.RChild != null)
        {
            return Search(p.RChild, value);
        }
        return null;
    }

    // 统计二叉树中的叶子结点数量
    int CountLeafNode(TreeNode<int> root)
    {
        if (root == null)
        {
            return 0;
        }

        else if (root.LChild == null && root.RChild == null)
        {
            return 1;
        }
        else
        {
            return CountLeafNode(root.LChild) + CountLeafNode(root.RChild);
        }
    }

    // 获取二叉树的深度
    int GetHeight(TreeNode<int> root)
    {
        int lh;
        int rh;

        if (root == null)
        {
            return 0;
        }
        else if (root.LChild == null && root.RChild == null)
        {
            return 1;
        }
        else
        {
            lh = GetHeight(root.LChild);
            rh = GetHeight(root.RChild);
            return (lh > rh ? lh : rh) + 1;
        }
    }

    // 构建二叉排序树
    public int Insert(BiTree<int> bt, int key)
    {
        TreeNode<int> p;
        TreeNode<int> parent = new TreeNode<int>();

        p = bt.Head;
        while (p != null)
        {
            if (p.Data == key)
            {
                Console.WriteLine("Record is exist");
                return 0;
            }
            parent = p;
            if (p.Data < key)
            {
                p = p.RChild;
            }
            else
            {
                p = p.LChild;
            }
        }
        p = new TreeNode<int>(key);
        if (parent == null)
        {
            bt.Head = p;
        }
        else if (p.Data < parent.Data)
        {
            parent.LChild = p;
        }
        else
        {
            parent.RChild = p;
        }
        return 1;
    }

    // 二叉排序树结点被删除
    public int Delete(BiTree<int> bt, int key)
    {
        TreeNode<int> p;
        TreeNode<int> parent = new TreeNode<int>();
        TreeNode<int> s = new TreeNode<int>();
        TreeNode<int> q = new TreeNode<int>();

        if (bt.IsEmpty())
        {
            Console.WriteLine("The Binary Sorting is empty");
            return 0;
        }
        p = bt.Head;
        parent = p;
        while (p != null)
        {
            if (p.Data == key)
            {
                // 是叶子结点
                if (bt.IsLeaf(p))
                {
                    if (p == bt.Head)
                    {
                        bt.Head = null;
                    }
                    else if (p == parent.LChild)
                    {
                        parent.LChild = null;
                    }
                    else
                    {
                        parent.RChild = null;
                    }
                }
                // 删除的结点右子结点为空而左子结点非空
                else if ((p.RChild == null) && (p.LChild != null))
                {
                    if (p == parent.LChild)
                    {
                        parent.LChild = p.LChild;
                    }
                    else
                    {
                        parent.RChild = p.LChild;
                    }
                }
                // 删除结点的左子结点为空而右子结点非空
                else if ((p.LChild == null) && (p.RChild != null))
                {
                    if (p == parent.LChild)
                    {
                        parent.LChild = p.RChild;
                    }
                    else
                    {
                        parent.RChild = p.RChild;
                    }
                }
                // 删除结点的左右子结点都非空
                else
                {
                    q = p;
                    s = p.RChild;
                    // 找到当前删除结点的右子树的最左边那个结点（这个值最小）
                    while (s.LChild != null)
                    {
                        q = s;
                        s = s.LChild;
                    }
                    p.Data = s.Data;// 将右边最小值赋予被删除的结点
                    // 处理最左边那个结点的移除工作
                    if (q != p)
                    {
                        q.LChild = s.RChild;
                    }
                    else
                    {
                        q.RChild = s.RChild;
                    }
                }
                return 1;
            }
            else if (p.Data < key)
            {
                parent = p;
                p = p.RChild;
            }
            else
            {
                parent = p;
                p = p.LChild;
            }
        }
        return 0;
    }
}
